package io.vector.study.algorithm.sort;

import org.apache.commons.collections.CollectionUtils;

import java.util.List;

/**
 * Created by vector on 2017/3/6.
 */
public class QuickSort implements SortStrategy {

    public <T extends Comparable<? super T>> void sort(List<T> list) {
        if (CollectionUtils.isEmpty(list)) {
            return ;
        }

        resolve(list, 0, list.size() - 1);
    }

    private <T extends Comparable<? super T>> void resolve(List<T> list, int start, int end) {
        if (start >= end) {
            return ;
        }

        int partition = partition(list, start, end);
        resolve(list, start, partition - 1);
        resolve(list, partition + 1, end);
    }

    private <T extends Comparable<? super T>> int partition(List<T> list, int start, int end) {
        if (start >= end) {
            return start;
        }

        int baseValueIndex = start;
        T baseValue = list.get(baseValueIndex);

        while (start < end) {
            while (start < end && list.get(end).compareTo(baseValue) > 0) --end;
            while (start < end && list.get(start).compareTo(baseValue) <= 0) ++start;
            if (start < end && start != end) {
                swap(list, start, end);
            }
        }

        swap(list, baseValueIndex, start);
        return start;
    }

    <T extends Comparable<? super T>> void swap(List<T> list, int index1, int index2) {
        if (index1 == index2) {
            return ;
        }

        T temp = list.get(index1);
        list.set(index1, list.get(index2));
        list.set(index2, temp);

//        System.out.println("index1: " + index1 + "\t index2: " + index2);
    }

}
